import collections


class Solution(object):
    def strongPasswordChecker(self, password):
        """
        :type password: str
        :rtype: int
        """
        n = len(password)
        flag1 = 0
        flag2 = 0
        flag3 = 0
        left = 0
        right = 0
        d = collections.defaultdict(int)
        steps = 0
        while right < n:
            if '0' <= password[right] <= '9':
                flag1 = 1
            if 'a' <= password[right] <= 'z':
                flag2 = 1
            if 'A' <= password[right] <= 'Z':
                flag3 = 1
            if password[right] != password[left]:
                if right - left >= 3:
                    d[right - left] += 1
                left = right
            right += 1
        if right - left >= 3:
            d[right - left] += 1
        d_needed = 0
        ver_needed = 0
        for key in d:
            ver_needed += (key // 3) * d[key]
            d_needed += (key - 2) * d[key]
        f_needed = 3 - flag1 - flag2 - flag3
        if n < 6:
            steps = max(6 - n, f_needed)
        if 6 <= n <= 20:
            steps = max(ver_needed, f_needed)
        if n > 20:
            if n - 20 >= d_needed:
                steps = n - 20 + f_needed
            else:
                d_needed = n - 20
                t_d = d_needed
                cn = [0, 0, 0]
                for key in d:
                    cn[key % 3] += d[key]
                if d_needed >= cn[0]:
                    d_needed -= cn[0]
                    ver_needed -= cn[0]
                else:
                    ver_needed -= d_needed
                    d_needed = 0
                if d_needed >= 2 * cn[1]:
                    d_needed -= 2 * cn[1]
                    ver_needed -= cn[1]
                else:
                    ver_needed -= d_needed // 2
                    d_needed = 0
                if d_needed > 0:
                    ver_needed -= d_needed // 3
                steps = t_d + max(ver_needed, f_needed)
        return steps


data = Solution()
password = "aA1"
print(data.strongPasswordChecker(password))
password = "133370d3"
print(data.strongPasswordChecker(password))
password = "absdsdffffeeeffAfefds"
print(data.strongPasswordChecker(password))
password = "bbaaaaaaaaaaaaaaacccccc"
print(data.strongPasswordChecker(password))
